<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="tutorial.css">
<TITLE>
Using Cut
</TITLE>
</HEAD>
<BODY >
<A HREF="tutorial019.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial012.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial021.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc44">3.8</A>&nbsp;&nbsp;Using Cut</H2><UL>
<LI><A HREF="tutorial020.html#toc26">Commit to current clause</A>
<LI><A HREF="tutorial020.html#toc27">Prune alternative solutions</A>
</UL>

<A NAME="cut"></A>
<A NAME="@default80"></A>
Cut (written as <CODE>!</CODE>) prunes away part of the Prolog search-space. This
can be a very powerful mechanism for improving the performance of programs,
and even the suppression of unwanted solutions. However, it can also be
easily misused and over-used. <BR>
<BR>
Cut does two things:
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>commit</B><DD CLASS="dd-description"> Disregard any later clauses for the predicate.
<DT CLASS="dt-description"><B>prune</B><DD CLASS="dd-description"> Throw away all alternative solutions to the goals to the left of
 the cut.
</DL>
<A NAME="toc26"></A>
<H3 CLASS="subsection"><A NAME="htoc45">3.8.1</A>&nbsp;&nbsp;Commit to current clause</H3>
<A NAME="@default81"></A>
Consider the following encoding of the &#8220;minimum&#8221; predicate:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
min(X,Y, Min) :- X &lt;Y, Min = X.
min(X,Y, Min) :- Y=&lt;X, Min = Y.
</PRE></BLOCKQUOTE></TD>
</TR></TABLE>
Whilst logically correct, the behaviour of this encoding is
non-optimal for two reasons. Consider the goal <TT>:- min(2,3,M)</TT>.
Although the first clause succeeds, correctly instantiating <I>M</I> to
2, Prolog leaves an open choice point. If these clauses and goal
occur as part of a larger program and goal, a failure might occur
later, causing backtracking to this open choice point. 
Prolog would then, in vain, try to find another minimum using the
second clause for <TT>min</TT>. So there is a double drawback:
firstly, an open choice point consumes memory, and secondly the
unsuccessful evaluation of the second clause costs execution time.<BR>
<BR>
To achieve the same logic, but more efficient behaviour, the
programmer can introduce a <I>cut</I>.
For example <TT>min</TT> is typically encoded as follows:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
min(X,Y, Min) :- X&lt;Y, !, Min = X.
min(X,Y, Y).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE>
The cut removes the unnecessary choice point, which means that the
second clause will never be executed if the first clause passed the
cut. This effectively makes the test in the second clause redundant,
and it can therefore be removed.<BR>
<BR>
<A NAME="toc27"></A>
<H3 CLASS="subsection"><A NAME="htoc46">3.8.2</A>&nbsp;&nbsp;Prune alternative solutions</H3>
<A NAME="@default82"></A>
A cut may occur anywhere where a goal may occur, consider the following:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
first_prime(X, P) :-
    prime(X,P), !.
</PRE></BLOCKQUOTE></TD>
</TR></TABLE>
where <CODE>first_prime</CODE> returns the first prime number smaller than <CODE>X</CODE>.
In this case, it calls a predicate <CODE>prime/2</CODE>, which generates prime
numbers smaller than <CODE>X</CODE>, starting from the largest one. The effect of
the cut here is to prune away all the remaining solutions to <CODE>prime(X,P)</CODE>
once the first one is generated, so that on backtracking, <CODE>prime(X,P)</CODE>
is not tried for alternative solutions. The cut will also commit the execution
to this clause for <CODE>first_prime/2</CODE>, but as there is only one clause,
this has no visible effect.<BR>
<BR>
<HR>
<A HREF="tutorial019.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial012.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial021.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
